using System;
using System.Text;
using ClearSpringNet.Hash;
using ClearSpringNet.Util;

namespace ClearSpringNet.Stream.Cardinality
{
    public class LinearCounting : ICardinality
    {
        protected byte[] map;
        protected int length;
        protected int count;

        public LinearCounting(int size)
        {
            this.length = 8 * size;
            this.count = this.length;
            map = new byte[size];
        }

        public LinearCounting(byte[] map)
        {
            this.map = map;
            this.length = 8 * map.Length;
            this.count = computeCount();
        }


        public bool Offer(object objectOffered)
        {
            bool modified = false;
            long hash = (long)MurmurHash.Hash(Encoding.Default.GetBytes(objectOffered.ToString()));
            int bit = (int)((hash & 0xFFFFFFFFL) % (long)length);
            int i = bit / 8;
            byte b = map[i];
            byte mask = (byte)(1 << (bit % 8));
            if ((mask & b) == 0)
            {
                map[i] = (byte)(b | mask);
                count--;
                modified = true;
            }
            return modified;
        }


        public long Cardinality()
        {
            return (long)(Math.Round(length * Math.Log(length / ((double)count))));
        }

        public int SizeOf()
        {
            return map.Length;
        }

        public byte[] GetBytes()
        {
            return map;
        }

        public ICardinality Merge(params ICardinality[] estimators)
        {
            var numEstimators = (estimators == null) ? 0 : estimators.Length;
            var lcs = new LinearCounting[numEstimators + 1];
            if (numEstimators > 0)
            {
                for (int i = 0; i < numEstimators; i++)
                {
                    if (estimators[i].GetType() is LinearCounting)
                    {
                        lcs[i] = (LinearCounting)estimators[i];
                    }
                    else
                    {
                        throw new Exception("Unable to merge LinearCounting with " + estimators[i].GetType().FullName);
                    }
                }
            }

            lcs[numEstimators] = this;
            return MergeEstimators(lcs);
        }

        public static LinearCounting MergeEstimators(params LinearCounting[] estimators)
        {
            LinearCounting merged = null;
            if (estimators != null && estimators.Length > 0)
            {
                int size = estimators[0].map.Length;
                byte[] mergedBytes = new byte[size];

                for (int e = 0; e < estimators.Length; e++)
                {
                    if (estimators[e].map.Length != size)
                    {
                        throw new Exception("Cannot merge estimators of different sizes");
                    }

                    for (int b = 0; b < size; b++)
                    {
                        mergedBytes[b] |= estimators[e].map[b];
                    }
                }

                merged = new LinearCounting(mergedBytes);
            }
            return merged;
        }

        protected int computeCount()
        {
            int c = 0;
            foreach (byte b in map)
            {
                c += Integer.BitCount(b & 0xFF);
            }
            return length - c;
        }


        public double getUtilization()
        {
            return (length - count) / (double)length;
        }


        public int getCount()
        {
            return count;
        }


        public bool isSaturated()
        {
            return (count == 0);
        }


        protected String mapAsBitString()
        {
            var sb = new StringBuilder(length);
            foreach (var b in map)
            {
                String bits = Integer.ToBinaryString(b);
                int leadingZeros = 8 - bits.Length;
                if (leadingZeros > 0)
                {
                    for (int i = 0; i < leadingZeros; i++) sb.Append('0');
                    sb.Append(bits);
                }
                else
                {
                    sb.Append(bits.Substring(bits.Length - 8, bits.Length));
                }
            }
            return sb.ToString();
        }


        [Serializable]
        public class Builder : IBuilder<ICardinality>
        {
            private static long serialVersionUID = -4245416224034648428L;

            /// <summary>
            /// Taken from Table II of Whang et al.
            /// </summary>
            private static int[] onePercentErrorLength =
            {
                5034, 5067, 5100, 5133, 5166, 5199, 5231, 5264, 5296,                    // 100 - 900
                5329, 5647, 5957, 6260, 6556, 6847, 7132, 7412, 7688,                    // 1000 - 9000
                7960, 10506, 12839, 15036, 17134, 19156, 21117, 23029, 24897,            // 10000 - 90000
                26729, 43710, 59264, 73999, 88175, 101932, 115359, 128514, 141441,       // 100000 - 900000
                154171, 274328, 386798, 494794, 599692, 702246, 802931, 902069, 999894,  // 1000000 - 9000000
                1096582                                                                  // 10000000
            };

            private int size;

            public Builder()
                : this(65536)
            {
            }

            public Builder(int size)
            {
                this.size = size;
            }


            public ICardinality build()
            {
                return new LinearCounting(size);
            }

            public int SizeOf()
            {
                return size;
            }

            /// <summary>
            /// Returns a LinearCounting.Builder that generates an LC
            /// estimator which keeps estimates below 1% error on average and has
            /// a low likelihood of saturation (0.7%) for any stream with
            /// cardinality less than maxCardinality
            /// </summary>
            /// <param name="maxCardinality"></param>
            /// <returns></returns>
            public static Builder onePercentError(int maxCardinality)
            {
                if (maxCardinality <= 0) throw new ArgumentException("maxCardinality (" + maxCardinality + ") must be a positive integer");

                int length = 
                    -1;
                if (maxCardinality < 100)
                {
                    length = onePercentErrorLength[0];
                }
                else if (maxCardinality < 10000000)
                {
                    int logscale = (int)Math.Log10(maxCardinality);
                    int scaleValue = (int)Math.Pow(10, logscale);
                    int scaleIndex = maxCardinality / scaleValue;
                    int index = 9 * (logscale - 2) + (scaleIndex - 1);
                    int lowerBound = scaleValue * scaleIndex;
                    length = lerp(lowerBound, onePercentErrorLength[index], lowerBound + scaleValue, onePercentErrorLength[index + 1], maxCardinality);

                    //System.out.println(String.format("Lower bound: %9d, Max cardinality: %9d, Upper bound: %9d", lowerBound, maxCardinality, lowerBound+scaleValue));
                    //System.out.println(String.format("Lower bound: %9d, Interpolated   : %9d, Upper bound: %9d", onePercentErrorLength[index], length, onePercentErrorLength[index+1]));
                }
                else if (maxCardinality < 50000000)
                {
                    length = lerp(10000000, 1096582, 50000000, 4584297, maxCardinality);
                }
                else if (maxCardinality < 100000000)
                {
                    length = lerp(50000000, 4584297, 100000000, 8571013, maxCardinality);
                }
                else if (maxCardinality <= 120000000)
                {
                    length = lerp(100000000, 8571013, 120000000, 10112529, maxCardinality);
                }
                else
                {
                    length = maxCardinality / 12;
                }

                int sz = (int)Math.Ceiling(length / 8D);

                //System.out.println("length: "+length+", size (bytes): "+sz);

                return new Builder(sz);
            }

            /**
             *
             * @param x0
             * @param y0
             * @param x1
             * @param y1
             * @param x
             * @return linear interpolation
             */
            protected static int lerp(int x0, int y0, int x1, int y1, int x)
            {
                return (int)Math.Ceiling(y0 + (x - x0) * (double)(y1 - y0) / (x1 - x0));
            }
        }


















    }


}